package leetcode.l0601;

import leetcode.l0526.TreeNode;

/**
 * @author Retain
 * @date 2021/6/1 10:24
 */
public class Easy_二叉树直径_543 {

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;
        diameterOfBinaryTree(t1);
    }

    static int max = 0;
    /**
     * 思路：转换题意：求边长最长，可能不经过根节点，递归求每个结点左右子树深度之和求最大值
     * @param root
     * @return
     */
    public static int diameterOfBinaryTree(TreeNode root) {
        if (root != null) {
            // 求深度
            getDepth(root);
            return max;
        }
        return 0;
    }

    /**
     * 深度优先求子树高度
     * @param root
     * @return
     */
    public static int getDepth(TreeNode root) {
        if (root != null) {
            // 一直进入左子树直到叶子结点，叶子结点left返回0
            int left = getDepth(root.left);
            // 左子树叶子结点返回后一直进入叶子结点父节点的右子树，右子树叶子结点返回0
            int right = getDepth(root.right);
            // 真实有效的执行已经返回到叶子结点的第一个父节点，将它左右子树高度相加
            if (left + right > max) {
                max = left + right;
            }
            // 返回孩子结点最长的一条子树高度 + 自身1高度
            return Math.max(left, right) + 1;
        }
        return 0;
    }
}
